#include <iostream>
#include <vector>

int dfs(std::vector<int>& nums,int target,int i,int j) {
    // 递归退出条件
    if(i > j) {
        return -1;
    }
    int m = i + (j - i) / 2;
    if(nums[m] > target) {
        return dfs(nums,target,i,m-1);
    }
    else if(nums[m] < target){
        return dfs(nums,target,m+1,j);
    }
    else {
        return m;
    }
}

int BinarySearchDfs(std::vector<int>& nums,const int target) {
    int n = nums.size();
    return dfs(nums,target,0,n-1);
}

void test() {
    std::vector<int> nums = {1,2,3,4,15,15,15,26,47,54,63,86,100};
    int target = 63;
    int target_id = 0;
    target_id = BinarySearchDfs(nums,target);
    std::cout << "target_id:" << target_id << std::endl;
    return;
}
int main()
{
    test();
    return 0;
}
